package com.example.Arithmetic.Arithmetic;

import java.util.Arrays;

/**
 * 日期：2023/12/27
 * 时间：9:00
 * 描述：希尔排序
 * 最后一层就是个插入排序，不过排序次数变少了
 */
public class ShellSort {
    public void sort(int[] ints) {
        for (int gap = ints.length >> 1; gap > 0; gap = gap >> 1) {
            for (int i = gap; i < ints.length; i++) {
                int t = ints[i];
                int w = i - gap;
                while (w >= 0 && t < ints[w]) {
                    ints[w + gap] = ints[w]; // 空出插入位置
                    w-=gap;
                }
                // 找到插入位置
                if (w != i - gap) {
                    ints[w + gap] = t;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 3, 1, 7, 6, 4, 5};
        System.out.println(Arrays.toString(a));
        ShellSort shellSort = new ShellSort();
        shellSort.sort(a);
        System.out.println(Arrays.toString(a));
    }
}
